/*
题目: 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

    '.' 匹配任意单个字符
    '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

https://leetcode.cn/problems/regular-expression-matching
 */
public class IsMatch {
    public boolean isMatch(String s, String p) {
        int slen = s.length();
        int plen = p.length();

        // s[:i] 和 p[:j] 是否能够匹配
        boolean[][] dp = new boolean[slen + 1][plen + 1];
        // 初始化
        dp[0][0] = true; // 为第一轮匹配提供条件
        // 字符和 '*' 可以组成空串
        for (int i = 2; i <= plen; i++) {
            if (p.charAt(i - 1) == '*') {
                // 舍弃这两个字符, 由于是初始化 s[0] 时的情况, 所以只有这种情况
                dp[0][i] = dp[0][i - 2];
            }
        }

        for (int i = 1; i <= slen; i++) {
            for (int j = 1; j <= plen; j++) {
                if (p.charAt(j - 1) == '*') {
                    // 可以舍弃
                    dp[i][j] |= dp[i][j - 2];
                    // 连续匹配多个字符, '*' 前的字符匹配, 或者 '*' 前是 '.', 那就都能匹配
                    // 匹配 s 末尾的一个字符，而该组合还可以继续进行匹配
                    if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
                        dp[i][j] |= dp[i - 1][j];
                    }
                } else if ((p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.')) {
                    dp[i][j] |= dp[i - 1][j - 1]; // 能够匹配的话, 取决于前面那个步骤
                }
            }
        }

        return dp[slen][plen];
    }
}
